/**
 * 1
 *  
 * @Author : roryrywang
 * @DateTime : 24-9-6 下午7:36
 */

#include <iostream>

using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串 提供的字符串
     * @return int整型
     */
    int longestPalindromeSubseq(string s) {
        int f[s.size()][s.size()];
        for (int len = 1; len <= s.size(); ++len) {
            for (int i = 0, j = i + len - 1; j < s.size(); ++i, ++j) {
                if (i == j) {
                    f[i][j] = 1;
                } else if (i + 1 == j) {
                    f[i][j] = s[i] == s[j] ? 2 : 1;
                } else {
                    f[i][j] = 0;
                    if (s[i] == s[j]) {
                        f[i][j] = f[i + 1][j - 1] + 2;
                    }else{
                        f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                    }
                }
            }
        }
        return f[0][s.size() - 1];
    }
};

int main() {
    Solution sl;
    cout << sl.longestPalindromeSubseq("bbbab");
    return 0;
};